package 面试经典150题.二叉树;

import common.TreeNode;

/**
 * @author tmh
 * @date 2024/6/22 21:10
 * @description 分析：BST 的中序遍历是升序的，因此本题等同于根据中序遍历的序列恢复二叉搜索树。
 * 因此我们可以以升序序列中的任一个元素作为根节点，以该元素左边的升序序列构建左子树，以该元素右边的升序序列构建右子树，
 * 这样得到的树就是一棵二叉搜索树啦～ 又因为本题要求高度平衡，因此我们需要选择升序序列的中间元素作为根节点奥～
 *

 */
public class T108将有序数组转换为二叉搜索树 {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums,0,nums.length-1);

    }

    private TreeNode dfs(int[] nums ,int low,int high){
        //如果left>right,返回null
        if(low>high){
            return null;
        }
        //得到中间元素的下标
        int mid = low + (high - low) / 2;
        // 以升序数组的中间元素作为根节点 root。
        TreeNode root = new TreeNode(nums[mid]);
        //往左遍历生成左子树
         root.left = dfs(nums, low, mid-1);
        //往右面遍历生成右子树
        root.right = dfs(nums, mid+1, high);
        return root;
    }
}
